This invention relates to a circuit and a method for determining a checksum for a digital data packet. The circuit and method of the invention find particular application in determining a checksum for a digital data packet under the Transmission Control Protocol (TCP).
In digital telecommunications, data is frequently conveyed in streams of data symbols or signals called `packets`. To allow verification of received data, the packets may include a code which can be derived from the transmitted data. One such type of code is a checksum, which is utilized in Transmission Control Protocol (TCP) packets. The checksum is calculated from the data to be transmitted in the packet, and added to the header of the packet along with other information such as source and destination indications, before transmission of the packet takes place. When the packet is received at the destination, the checksum is retrieved from the packet header, and a new checksum is calculated from the received packet data. The received checksum and the newly calculated checksum are then compared, with any discrepancy indicating that the received packet does not precisely match the packet as it was transmitted.
One way in which a checksum can be generated for a packet to be transmitted is to utilize the host processor, from which the data packet originates, to calculate the checksum before the data is passed to the telecommunications interface for transmission. In this case the checksum is generated using a software algorithm to control a general purpose processor. Although this system requires no additional hardware to implement the checksum provision and the data packets can be assembled before leaving the host processor, generating the checksums can place an undesirable burden on the host processor and is not an optimum allocation of the host processing resources.
Since the checksum value for a data packet can only be determined when all of the data to be transmitted in the packet has been assembled, the checksum generation can be performed in the telecommunications interface which couples the host processor to the telecommunications network. A multipurpose processing circuit under software control could be employed for this purpose. However, it is generally desirable to provide as many of the telecommunications interface functions as possible on a single integrated circuit, in which case a dedicated checksum generation circuit may be more efficient in terms of silicon area required. Also, with the checksum being determined at the telecommunications interface, it is necessary to generate the checksum for packets `on the fly`, which also recommends a fast and compact dedicated summing circuit.
In order to calculate a 16 bit TCP checksum it is necessary to take the 16 bit one's complement sum of the TCP packet data. In essence this requires that all of the 16 bit data be summed, with the carry-out from the 16 bit result being added into the sum. One way in which such a sum can be achieved is to sequentially sum all of the 16 bit data using an adder which produces a greater than 16 bit result, and then adding the most significant bits exceeding the desired 16 bit sum (i.e. the collective carry for the 16 bit additions) back into the 16 bit checksum for two addition cycles. However, the adder circuit required to generate the checksum In this way can be prohibitively complex, particularly when a relatively large packet is to be dealt with.
The complexity of generating a 16 bit TCP checksum is further compounded when the packet input data path is 32 bits wide, given that the checksum is to be generated on the fly. In that case, unless the checksum generator is able to operate at twice the speed as the incoming data, a 32 bit per processing cycle data input capability is required. Thus, according to the checksum generation strategy outlined above, either a single very complex adder circuit with 32 bit input paths and a greater than 32 bit output would be required, or a pair of 16 bit input adders with collective carry-outputs (i.e. greater than 16 bit sum output), as well as additional circuitry and summing cycles, would be required in order to produce a 16 bit checksum result.
Accordingly, it is one object of the invention to provide for the generation of a TCP checksum in a circuit with a minimum number and complexity of circuit elements, as well as a minimum of processing cycles.
It is another object of the invention to provide a checksum generation circuit which can be implemented in a telecommunications interface integrated circuit for generating checksum values for data packets on the fly.
It is also an object of the invention to provide a method of sequentially processing a data stream so as to generate a checksum in a minimum number of processing cycles.